package src.leetcode.everyday.mid_1594;

/**
 * @author liyizzz
 * @description 矩阵的最大非负积
 * @date 2025/1/14 17:12
 */
public class maxProductPath {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxProductPath(new int[][]{{1,-1,2,1,-1,0,0,4,3,2,0,-2,-2},{-2,3,3,-1,-1,0,0,-2,4,-3,3,0,0},{-4,-1,-1,-2,2,-1,-2,-2,0,3,-1,-4,1},{-3,4,-3,0,-3,1,-3,1,4,4,-4,-4,-2},{3,-3,1,0,-1,-4,-4,-4,3,2,2,3,3},{2,-1,-1,-4,-3,-3,4,2,3,4,4,-4,0},{4,-1,2,-3,-1,-1,-3,-4,4,4,4,-3,-1},{-3,-4,4,-2,-1,2,3,-1,2,3,4,4,-4},{-3,-1,-2,1,1,-1,-3,-4,-3,1,-3,3,-4},{2,4,4,4,-3,-3,1,-1,3,4,-1,1,4},{2,-2,0,4,-1,0,-2,4,-4,0,0,2,-3},{1,1,-3,0,-4,-4,-4,-4,0,-1,-4,-1,0},{3,-1,-3,-3,-3,-2,-1,4,-1,-2,4,2,3}} ));
    }
}
class Solution {
    public int maxProductPath(int[][] grid) {
        int mod = 1000_000_007;
        int n = grid.length, m = grid[0].length;
        int[][][] dp = new int[n][m][2];
        if (grid[0][0] > 0) {
            dp[0][0][0] = Math.abs(grid[0][0]);
        } else {
            dp[0][0][1] = Math.abs(grid[0][0]);
        }

        for (int j = 1; j < m; j++) {
            dp[0][j][0] = (Math.abs(grid[0][j]) * dp[0][j - 1][0]) % mod;
            dp[0][j][1] = (Math.abs(grid[0][j]) * dp[0][j - 1][1]) % mod;
            if (grid[0][j] < 0) {
                swap(dp[0][j]);
            }
        }

        for (int i = 1; i < n; i++) {
            dp[i][0][0] = (Math.abs(grid[i][0]) * dp[i - 1][0][0]) % mod;
            dp[i][0][1] = (Math.abs(grid[i][0]) * dp[i - 1][0][1]) % mod;
            if (grid[i][0] < 0) {
                swap(dp[i][0]);
            }
            for (int j = 1; j < m; j++) {
                long c1 = (long) Math.abs(grid[i][j]) * dp[i - 1][j][0];
                long c2 = (long) Math.abs(grid[i][j]) * dp[i - 1][j][1];
                long c3 = (long) Math.abs(grid[i][j]) * dp[i][j - 1][0];
                long c4 = (long) Math.abs(grid[i][j]) * dp[i][j - 1][1];
                dp[i][j][0] = (int) (Math.max(c1, c3) % mod);
                dp[i][j][1] = (int) (Math.max(c2, c4) % mod);
                if (grid[i][j] < 0) {
                    swap(dp[i][j]);
                }
            }
        }

        boolean isExist = false;
        for (int[] ints : grid) {
            for (int j = 0; j < m; j++) {
                if (ints[j] == 0) {
                    isExist = true;
                    break;
                }
            }
            if (isExist) {
                break;
            }
        }

        if (dp[n - 1][m - 1][0] > 0) {
            return dp[n - 1][m - 1][0];
        }
        return isExist? 0 : -1;
    }

    private void swap(int[] nums) {
        int t = nums[0];
        nums[0] = nums[1];
        nums[1] = t;
    }
}